package GreedyAlgorithm;

import java.util.Arrays;
import java.util.Comparator;

/**
 * kruskal算法实现最小生成树
 *
 * @author: luo
 * @email: luo@nyist.edu.cn
 * @date: 2020/12/24 15:45
 */
public class MSTKruskal {
    public static void main(String[] args) {
        int n = 6;
        int m = 10;

        int[][] edge = new int[][]{{0, 0, 0},
                {1, 2, 6}, {1, 3, 1}, {1, 4, 5}, {2, 3, 5}, {2, 5, 3},
                {3, 4, 5}, {3, 5, 6}, {3, 6, 4}, {4, 6, 2}, {5, 6, 7}};

        int[] item = kruskal(n, m, edge);
        int num = 0;
        for (int i = 1; i <= m; i++) {
            if (item[i] == 1) {
                System.out.println(edge[i][0] + "-->" + edge[i][1]);
                num += edge[i][2];
            }
        }
        System.out.println("-----" + num + "------");
    }

    /**
     * kruskal算法实现最小生成树
     * @param n 图的顶点数
     * @param m 图的边数
     * @param edge edge[i] 第i条边的信息
     * @return 解空间item[i]==1第i条边加入
     */
    static int[] kruskal(int n, int m, int[][] edge) {
        int[] item = new int[m + 1]; //作为解空间
        int[] fa = new int[n + 1];//记录当前节点的根节点节点
        for (int i = 1; i <= n; i++) fa[i] = i;//初始化
        Arrays.sort(edge, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[2], o2[2]);
            }
        });
        for (int i = 1; i <= m; i++) {
            int a = edge[i][0];
            int b = edge[i][1];
            if (listener(fa)) break;//完成
            if (get(fa,a)==get(fa,b)) continue; //同一根节点形成闭环，舍弃
            merge(fa, a, b); // 修改根节点
            item[i] = 1; // 加入解空间
        }
        return item;
    }

    /**
     * 判断是否完成 只有一棵树（一个根节点）时则构建完成
     * @param fa
     * @return
     */
    static boolean listener(int[] fa) {
        int n = 0;
        for (int i = 1; i <fa.length ; i++) {
            if (fa[i] == i) n++;
            if (n > 1) return false;
        }
        return true;
    }

    /**
     * 修改根节点
     * @param fa
     * @param a
     * @param b
     */
    private static void merge(int[] fa, int a, int b) {
        fa[get(fa, b)] = get(fa, a);
        fa[b] = get(fa, a);
    }

    /**
     * 获取根节点
     * @param fa
     * @param x
     * @return
     */
    static int get(int fa[], int x) {
        if (fa[x]== x) return fa[x];
        return get(fa, fa[x]);
    }

}
